Threshold logic (TL) has long been known as an alternative way to compute Boolean functions. Much of the earlier work on TL dates back to the 1960s, which focused primarily on exploring the theoretical aspects of TL, with little attention being paid to the synthesis and optimization of large, multi-level TL circuits, which are also referred to herein as TL networks. The lack of efficient implementations of TL gates, when compared to static fully Complementary Metal Oxide Semiconductor (CMOS) transistor networks and the rapid development of synthesis and optimization tools for Boolean logic design, led to a loss of interest in developing a similar infrastructure for designing TL circuits. The situation is now changing in favor of threshold logic.
The scaling of Metal Oxide Semiconductor Field Effect Transistors (MOSFETs) that has been taking place for over three decades is expected to continue for at least another decade, after which a point will be reached where transitioning to non-CMOS technologies will be necessary. Research is currently in progress to find the best alternative to CMOS. A few examples of post-CMOS devices are resonant tunneling diodes (RTDs), single electron transistors (SETs), quantum cellular automata (QCA), and carbon nano-tube FETs (CNT-FETs). A common and important characteristic of these devices is that they can be used to realize TL efficiently. Efficient CMOS implementations of threshold gates are also currently available. Consequently, there has been a resurgence of interest in TL and synthesis and verification methods that are applicable to large, multi-level threshold circuits.
The traditional approach for the synthesis of multilevel threshold logic circuits is based on determining if a Boolean function is threshold by verifying satisfiability of a large number of integer linear inequalities. However, such an approach is only practical for functions with a few inputs. Thus, there is a need for a method for synthesizing multilevel threshold circuits that eliminates the use of integer linear programming (ILP) formulation to determine if a Boolean function is threshold and to evaluate the weights and threshold in case the function is a threshold function.